package binary_tree.leetcode.medium;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author bruin_du
 * @description 二叉搜索树中的中序后继
 * @date 2022/8/15 21:56
 **/
public class OfferII053_InorderSuccessor {
    TreeNode target;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        //方法一：直接递归
        method1(root, p);

        //方法二：用全局变量保存
        method2(root, p);

        //方法三：用中序迭代
        return method3(root, p);
    }

    private TreeNode method1(TreeNode root, TreeNode p) {
        if (root == null) return null;
        TreeNode left = inorderSuccessor(root.left, p);
        if (left != null) return left;
        if (root.val > p.val) return root;
        return inorderSuccessor(root.right, p);
    }

    private TreeNode method2(TreeNode root, TreeNode p) {
        dfs(root, p);
        return target;
    }

    void dfs(TreeNode root, TreeNode p) {
        if (target != null || root == null) return;
        dfs(root.left, p);
        if (root.val > p.val && target == null) target = root;
        dfs(root.right, p);
    }

    private TreeNode method3(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            if (node.val > p.val && target == null) {
                target = node;
                break;
            }
            cur = node.right;
        }
        return target;
    }
}
